# 使用动态规划求解最长公共子序列(子序列可以不连续)
# 动态规划将原问题拆解成多个离散的子问题，逐步计算子问题的解最终获得原问题的解
def lcs_length(x: str, y: str):
    len_x, len_y = len(x), len(y)
    dp = [[0] * (len_x + 1) for _ in range(len_y + 1)]
    for i in range(1, len(x) + 1):
        for j in range(1, len(y) + 1):
            if x[i - 1] == y[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    i, j = len_x, len_y
    lcs = list()
    while i > 0 and j > 0:
        if x[i - 1] == y[j - 1]:
            lcs.append(x[i - 1])
            i -= 1
            j -= 1
        elif dp[i - 1][j] > dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    lcs = lcs[::-1]
    return dp, ''.join(lcs)

# 对于求解最长公共子串的递归公式(子序列必须连续)：
# if x[i] == y[j], dp[i][j] = dp[i-1][j-1] + 1
# if x[i] != y[j], dp[i][j] = 0
